package algorithm.niuke;

import java.util.Arrays;

/**
 * 重建二叉树
 *
 * @author jack.wu
 * @version 1.0
 * @date 2020-05-07
 */
public class ReconstructionBinaryTree {

    public static void main(String[] args) {
        int[] pre = {1, 2, 4, 7, 3, 5, 6, 8};
        int[] in = {4, 7, 2, 1, 5, 3, 8, 6};

        TreeNode root = reConstructBinaryTree(pre, in);
        System.out.println(root);


    }

    /**
     * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树
     * 思路：
     * 因为是树的结构，一般都是用递归来实现。
     * 用数学归纳法的思想就是，假设最后一步，就是root的左右子树都已经重建好了，那么我只要考虑将root的左右子树安上去即可。
     * 根据前序遍历的性质，第一个元素必然就是root，那么下面的工作就是如何确定root的左右子树的范围。
     * 根据中序遍历的性质，root元素前面都是root的左子树，后面都是root的右子树。那么我们只要找到中序遍历中root的位置，就可以确定好左右子树的范围。
     * 正如上面所说，只需要将确定的左右子树安到root上即可。递归要注意出口，假设最后只有一个元素了，那么就要返回。
     *
     * @param pre 前序数组
     * @param in  中序数组
     * @return 二叉树
     */
    private static TreeNode reConstructBinaryTree(int[] pre, int[] in) {

        // 校验
        if (pre == null || in == null || pre.length == 0 || in.length == 0) {
            return null;
        }

        // 根据前序遍历得到root
        int rootVal = pre[0];
        TreeNode root = new TreeNode(rootVal);

        // 在中序遍历中找到root的位置
        int rootIndex = 0;
        while (rootIndex < in.length) {
            if (rootVal == in[rootIndex]) {
                break;
            }
            rootIndex++;
        }

        // 递归，假设root的左右子树都已经构建完毕，那么只要将左右子树安到root左右即可
        root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, rootIndex + 1), Arrays.copyOfRange(in, 0, rootIndex));
        root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, rootIndex + 1, pre.length), Arrays.copyOfRange(in, rootIndex + 1, in.length));

        return root;
    }
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "val=" + val +
                ", left=" + left +
                ", right=" + right +
                '}';
    }
}
